package com.gitee.wsl.doc.prosemirror.model.content

import com.gitee.wsl.doc.prosemirror.model.expr.Expr
import com.gitee.wsl.doc.prosemirror.model.node.NodeType


fun resolveName(stream: TokenStream, name: String): List<NodeType> {
    val types = stream.nodeTypes
    val type = types[name]
    if (type != null) return listOf(type)
    val result = mutableListOf<NodeType>()
    for (typeName in types.keys) {
        types[typeName]?.let {
            if (it.isInGroup(name)) {
                result.add(it)
            }
        }
    }
    return result
}

// The code below helps compile a regular-expression-like language into a deterministic finite
// automaton. For a good introduction to these concepts, see
// https://swtch.com/~rsc/regexp/regexp1.html
class Edge(val term: NodeType?, var to: Int?)

// Construct an NFA from an expression as returned by the parser. The
// NFA is represented as an array of states, which are themselves
// arrays of edges, which are `{term, to}` objects. The first state is
// the entry state and the last node is the success state.
//
// Note that unlike typical NFAs, the edge ordering in this one is
// significant, in that it is used to contruct filler content when
// necessary.
fun nfa(expr: Expr): List<List<Edge>> {
    val nfa = mutableListOf<MutableList<Edge>>(mutableListOf())
    connect(compile(nfa, expr, 0), node(nfa))
    return nfa
}

fun node(nfa: MutableList<MutableList<Edge>>): Int {
    nfa.add(mutableListOf())
    return nfa.size - 1
}

fun edge(nfa: MutableList<MutableList<Edge>>, from: Int, to: Int? = null, term: NodeType? = null): Edge {
    val edge = Edge(term, to)
    nfa[from].add(edge)
    return edge
}

fun connect(edges: List<Edge>, to: Int) {
    edges.forEach { edge -> edge.to = to }
}

fun compile(nfa: MutableList<MutableList<Edge>>, expr: Expr, from: Int): List<Edge> {
    var thisFrom = from
    when (expr) {
        is Expr.Choice -> {
            val res = mutableListOf<Edge>()
            for (thisExpr in expr.exprs) {
                res.addAll(compile(nfa, thisExpr, thisFrom))
            }
            return res
        }

        is Expr.Seq -> {
            var i = 0
            while (true) {
                val next = compile(nfa, expr.exprs[i], thisFrom)
                if (i == expr.exprs.size - 1) return next
                thisFrom = node(nfa)
                connect(next, thisFrom)
                i++
            }
        }

        is Expr.Star -> {
            val loop = node(nfa)
            edge(nfa, thisFrom, loop)
            connect(compile(nfa, expr.expr, loop), loop)
            return listOf(edge(nfa, loop))
        }

        is Expr.Plus -> {
            val loop = node(nfa)
            connect(compile(nfa, expr.expr, thisFrom), loop)
            connect(compile(nfa, expr.expr, loop), loop)
            return listOf(edge(nfa, loop))
        }

        is Expr.Opt -> {
            return listOf(edge(nfa, thisFrom)) + compile(nfa, expr.expr, thisFrom)
        }

        is Expr.Range -> {
            var cur = thisFrom
            for (i in 0 until expr.min) {
                val next = node(nfa)
                connect(compile(nfa, expr.expr, cur), next)
                cur = next
            }
            if (expr.max == -1) {
                connect(compile(nfa, expr.expr, cur), cur)
            } else {
                for (i in expr.min until expr.max) {
                    val next = node(nfa)
                    edge(nfa, cur, next)
                    connect(compile(nfa, expr.expr, cur), next)
                    cur = next
                }
            }
            return listOf(edge(nfa, cur))
        }

        is Expr.Name -> {
            return listOf(edge(nfa, thisFrom, null, expr.value))
        }
    }
}

fun cmp(a: Int, b: Int): Int {
    return b - a
}

// Get the set of nodes reachable by null edges from `node`. Omit nodes with only a single
// null-out-edge, since they may lead to needless duplicated nodes.
fun nullFrom(nfa: List<List<Edge>>, node: Int): List<Int> {
    val result = mutableListOf<Int>()
    var scan: ((node: Int) -> Unit)? = null
    scan = { thisNode: Int ->
        val edges = nfa[thisNode]
        if (edges.size == 1 && edges[0].term == null) {
            scan?.invoke(edges.first().to!!)
        } else {
            result.add(thisNode)
            edges.forEach {
                val term = it.term
                val to = it.to
                if (term == null && result.indexOf(to!!) == -1) {
                    scan?.invoke(to)
                }
            }
        }
    }
    scan(node)
    result.sortWith(Comparator(::cmp))
    return result.toList()
}

// Compiles an NFA as produced by `nfa` into a DFA, modeled as a set of state objects
// (`ContentMatch` instances) with transitions between them.
fun dfa(nfa: List<List<Edge>>): ContentMatch {
    val labeled = mutableMapOf<String, ContentMatch>()
    return explore(nfa, labeled, nullFrom(nfa, 0))
}

@Suppress("NestedBlockDepth")
fun explore(nfa: List<List<Edge>>, labeled: MutableMap<String, ContentMatch>, states: List<Int>): ContentMatch {
    val out = mutableListOf<Pair<NodeType, MutableList<Int>>>()
    states.forEach { node ->
        nfa[node].forEach inner@{
            val term = it.term ?: return@inner
            val to = it.to
            var set: MutableList<Int>? = null
            for (i in 0 until out.size) {
                if (out[i].first == term) {
                    set = out[i].second
                }
            }
            nullFrom(nfa, to!!).forEach { node ->
                if (set == null) {
                    set = mutableListOf()
                    out.add(term to set)
                }
                if (set.indexOf(node) == -1) {
                    set.add(node)
                }
            }
        }
    }
    val state = ContentMatch(states.indexOf(nfa.size - 1) > -1)
    labeled[states.joinToString(",")] = state
    for (i in 0 until out.size) {
        val thisStates = out[i].second.sortedWith(::cmp)
        state.next.add(
            MatchEdge(
                type = out[i].first,
                next = labeled[thisStates.joinToString(",")] ?: explore(nfa, labeled, thisStates)
            )
        )
    }
    return state
}

fun ContentMatch.checkForDeadEnds(stream: TokenStream) {
    val work = mutableListOf(this)
    var i = 0
    while (i < work.size) {
        val state = work[i]
        var dead = !state.validEnd
        val nodes = mutableListOf<String>()
        state.next.forEach {
            val type = it.type
            val next = it.next
            nodes.add(type.name)
            if (dead && !(type.isText || type.hasRequiredAttrs())) {
                dead = false
            }
            if (work.indexOf(next) == -1) work.add(next)
        }
        if (dead) {
            stream.err(
                "Only non-generatable nodes (${nodes.joinToString(", ")}) in a required " +
                    "position (see https://prosemirror.net/docs/guide/#generatable)"
            )
        }
        i++
    }
}
